//Given an m x n board of characters and a list of strings words, return all 
//words on the board. 
//
// Each word must be constructed from letters of sequentially adjacent cells, 
//where adjacent cells are horizontally or vertically neighboring. The same letter 
//cell may not be used more than once in a word. 
//
// 
// Example 1: 
//
// 
//Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i",
//"f","l","v"]], words = ["oath","pea","eat","rain"]
//Output: ["eat","oath"]
// 
//
// Example 2: 
//
// 
//Input: board = [["a","b"],["c","d"]], words = ["abcb"]
//Output: []
// 
//
// 
// Constraints: 
//
// 
// m == board.length 
// n == board[i].length 
// 1 <= m, n <= 12 
// board[i][j] is a lowercase English letter. 
// 1 <= words.length <= 3 * 10⁴ 
// 1 <= words[i].length <= 10 
// words[i] consists of lowercase English letters. 
// All the strings of words are unique. 
// 
// Related Topics 字典树 数组 字符串 回溯 矩阵 👍 582 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class P212WordSearchIi {
    public static void main(String[] args) {
        Solution solution = new P212WordSearchIi().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        class TrieNode {
            String s;
            TrieNode[] tns = new TrieNode[26];
        }

        void insert(String s) {
            TrieNode p = root;
            for (int i = 0; i < s.length(); i++) {
                int u = s.charAt(i) - 'a';
                if (p.tns[u] == null) p.tns[u] = new TrieNode();
                p = p.tns[u];
            }
            p.s = s;
        }

        Set<String> set = new HashSet<>();
        char[][] board;
        int n, m;
        TrieNode root = new TrieNode();
        int[][] dirs = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        boolean[][] vis = new boolean[15][15];

        public List<String> findWords(char[][] _board, String[] words) {
            board = _board;
            m = board.length;
            n = board[0].length;
            for (String w : words) insert(w);
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    int u = board[i][j] - 'a';
                    if (root.tns[u] != null) {
                        vis[i][j] = true;
                        dfs(i, j, root.tns[u]);
                        vis[i][j] = false;
                    }
                }
            }
            List<String> ans = new ArrayList<>();
            for (String s : set) ans.add(s);
            return ans;
        }

        void dfs(int i, int j, TrieNode node) {
            if (node.s != null) set.add(node.s);
            for (int[] d : dirs) {
                int dx = i + d[0], dy = j + d[1];
                if (dx < 0 || dx >= m || dy < 0 || dy >= n) continue;
                if (vis[dx][dy]) continue;
                int u = board[dx][dy] - 'a';
                if (node.tns[u] != null) {
                    vis[dx][dy] = true;
                    dfs(dx, dy, node.tns[u]);
                    vis[dx][dy] = false;
                }
            }
        }

/*        Set<String> set = new HashSet<>();
        List<String> ans = new ArrayList<>();
        char[][] board;
        int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
        int n, m;
        boolean[][] vis = new boolean[15][15];
        public List<String> findWords(char[][] _board, String[] words) {
            board = _board;
            m = board.length; n = board[0].length;
            for (String w : words) set.add(w);
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    vis[i][j] = true;
                    sb.append(board[i][j]);
                    dfs(i, j, sb);
                    vis[i][j] = false;
                    sb.deleteCharAt(sb.length() - 1);
                }
            }
            return ans;
        }
        void dfs(int i, int j, StringBuilder sb) {
            if (sb.length() > 10) return ;
            if (set.contains(sb.toString())) {
                ans.add(sb.toString());
                set.remove(sb.toString());
            }
            for (int[] d : dirs) {
                int dx = i + d[0], dy = j + d[1];
                if (dx < 0 || dx >= m || dy < 0 || dy >= n) continue;
                if (vis[dx][dy]) continue;
                vis[dx][dy] = true;
                sb.append(board[dx][dy]);
                dfs(dx, dy, sb);
                vis[dx][dy] = false;
                sb.deleteCharAt(sb.length() - 1);
            }
        }*/
    }
//leetcode submit region end(Prohibit modification and deletion)

}